class Solution
{
    string _NUMTOSTR[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
    void Combinations(const string& digits, size_t di, string combinser, vector<string>& str)
    {
        if (di == digits.size())
        {
            str.push_back(combinser);
            return;
        }
        int num = digits[di] - '0';
        string strV = _NUMTOSTR[num];
        for (auto ch : strV)
        {
            Combinations(digits, di + 1, combinser + ch, str);
        }
    }
public:
    vector<string> letterCombinations(string digits)
    {
        vector<string> str;
        if (digits.size() == 0)
        {
            return str;
        }
        Combinations(digits, 0, "", str);
        return str;
    }
};